{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Leftmost Column with at Least a One"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #interactive #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #交互 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leftMostColumnWithOne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #至少有一个 1 的最左端列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><em>（这是一个<strong>交互题</strong>）</em></p>\n",
    "\n",
    "<p>我们称只包含元素&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>&nbsp;的矩阵为二进制矩阵。矩阵中每个<strong>单独</strong>的行都按非递减顺序排序。</p>\n",
    "\n",
    "<p>给定一个这样的二进制矩阵，返回至少包含一个&nbsp;<code>1</code>&nbsp;的最左端列的索引（从 0 开始）。如果这样的列不存在，返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p><strong>您不能直接访问该二进制矩阵。</strong>你只可以通过&nbsp;<code>BinaryMatrix</code>&nbsp;接口来访问。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>BinaryMatrix.get(row, col)</code>&nbsp;返回位于索引&nbsp;<code>(row, col)</code>&nbsp;（从 0 开始）的元素。</li>\n",
    "\t<li><code>BinaryMatrix.dimensions()</code>&nbsp;返回含有 2 个元素的列表&nbsp;<code>[rows, cols]</code>，表示这是一个&nbsp;<code>rows *&nbsp;cols</code>的矩阵。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果提交的答案调用&nbsp;<code>BinaryMatrix.get</code>&nbsp;超过 <code>1000</code> 次，则该答案会被判定为<em>错误答案</em>。提交任何试图规避判定机制的答案将会被取消资格。</p>\n",
    "\n",
    "<p>下列示例中，&nbsp;<code>mat</code>&nbsp;为给定的二进制矩阵。您不能直接访问该矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-5.jpg\" style=\"height:81px; width:81px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> mat = [[0,0],[1,1]]\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-4.jpg\" style=\"height:81px; width:81px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> mat = [[0,0],[0,1]]\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-3.jpg\" style=\"height:81px; width:81px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> mat = [[0,0],[0,0]]\n",
    "<strong>输出:</strong> -1</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-6.jpg\" style=\"height:121px; width:161px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rows == mat.length</code></li>\n",
    "\t<li><code>cols == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= rows, cols&nbsp;&lt;= 100</code></li>\n",
    "\t<li><code>mat[i][j]</code>&nbsp;只会是&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>。</li>\n",
    "\t<li><code>mat[i]</code>&nbsp;已按非递减顺序排序。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [leftmost-column-with-at-least-a-one](https://leetcode.cn/problems/leftmost-column-with-at-least-a-one/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [leftmost-column-with-at-least-a-one](https://leetcode.cn/problems/leftmost-column-with-at-least-a-one/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[1,1]]', '[[0,0],[0,1]]', '[[0,0],[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        m, n = binaryMatrix.dimensions()\n",
    "        ans = n\n",
    "        for i in range(m):\n",
    "            l, r = 0, n-1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if binaryMatrix.get(i, mid):\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            ans = min(ans, l)\n",
    "        return ans if ans < n else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        m, n = binaryMatrix.dimensions() # binary not Binary\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            start, end = 0, n -1\n",
    "            while start + 1 < end:\n",
    "                mid = (start + end)//2\n",
    "                if binaryMatrix.get(i, mid) == 1: # .get!!! don't miss i\n",
    "                    end = mid\n",
    "                else:\n",
    "                    start = mid\n",
    "            if binaryMatrix.get(i, start) == 1: # i,\n",
    "                res = min(res, start) # start first\n",
    "            elif binaryMatrix.get(i, end) == 1: # i,\n",
    "                res = min(res, end)\n",
    "        return res if res != float('inf') else -1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        m, n = binaryMatrix.dimensions()\n",
    "        res = n\n",
    "        for i in range(m):\n",
    "            start, end = 0, n -1\n",
    "            while start + 1 < end:\n",
    "                mid = (start + end)//2\n",
    "                if binaryMatrix.get(i, mid) == 1:\n",
    "                    end = mid\n",
    "                else:\n",
    "                    start = mid\n",
    "            tmp = n # must have\n",
    "            if binaryMatrix.get(i, start) == 1:\n",
    "                tmp = start\n",
    "            elif binaryMatrix.get(i, end) == 1:\n",
    "                tmp = end\n",
    "            res = min(res, tmp) # local variable 'tmp' referenced before assignment\n",
    "        return res if res != n else -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        \n",
    "        def biSearch(row, l, r):\n",
    "            while l != r:\n",
    "                mid = (l+r)//2\n",
    "                if binaryMatrix.get(row, mid) == 1:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            return l\n",
    "        \n",
    "        m,n = binaryMatrix.dimensions()\n",
    "\n",
    "        min_left = n\n",
    "        for r in range(m):\n",
    "            l = biSearch(r, 0, min_left)\n",
    "            min_left = min(l, min_left)\n",
    "        \n",
    "        if min_left >= n:\n",
    "            return -1\n",
    "        else:\n",
    "            return min_left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        \n",
    "        def biSearch(row, l, r):\n",
    "            while l != r:\n",
    "                mid = (l+r)//2\n",
    "                if binaryMatrix.get(row, mid) == 1:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            return l\n",
    "        \n",
    "        m,n = binaryMatrix.dimensions()\n",
    "\n",
    "        min_left = n\n",
    "        for r in range(m):\n",
    "            l = biSearch(r, 0, min_left)\n",
    "            min_left = min(l, min_left)\n",
    "        \n",
    "        if min_left >= n:\n",
    "            return -1\n",
    "        else:\n",
    "            return min_left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        n, m = binaryMatrix.dimensions()\n",
    "        ans = m + 1\n",
    "\n",
    "        for i in range(n):\n",
    "            left = 0\n",
    "            right = m - 1\n",
    "            if binaryMatrix.get(i, left):\n",
    "                return 0\n",
    "            if binaryMatrix.get(i, right) == 0:\n",
    "                continue\n",
    "            while left < right - 1:\n",
    "                mid = (left + right) // 2\n",
    "                if binaryMatrix.get(i, mid):\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            ans = min(ans, right)\n",
    "        \n",
    "        return -1 if ans == m + 1 else ans\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, data: 'BinaryMatrix') -> int:\n",
    "        def get_first_one_idx(cur_row):\n",
    "            left, right = 0, cols - 1\n",
    "            while left < right:\n",
    "                mid = left + ((right - left) >> 1)\n",
    "                if data.get(cur_row, mid) == 1:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left if left < cols and data.get(cur_row, left) == 1 else inf\n",
    "\n",
    "        rows, cols = data.dimensions()\n",
    "        result = inf\n",
    "        for i in range(rows):\n",
    "            cur_result = get_first_one_idx(i)\n",
    "            result = min(result, cur_result)\n",
    "        return result if result != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        m, n = binaryMatrix.dimensions()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(x, y):\n",
    "            return binaryMatrix.get(x, y)\n",
    "            \n",
    "        ans = n + 1\n",
    "        for i in range(m):\n",
    "            j = 0\n",
    "            k = min(n - 1, ans)\n",
    "            while j < k - 1:\n",
    "                mid = j + (k - j) // 2\n",
    "                if check(i, mid) == 1:\n",
    "                    k = mid\n",
    "                else:\n",
    "                    j = mid\n",
    "            if j < ans and check(i, j) == 1:\n",
    "                ans = j\n",
    "            if k < ans and check(i, k) == 1:\n",
    "                ans = k\n",
    "        return ans if ans < n + 1 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        m, n = binaryMatrix.dimensions()\n",
    "        def binarySearch(i):\n",
    "            left, right = 0, n - 1\n",
    "            while left <= right:\n",
    "                mid  = left + (right - left)//2\n",
    "                if binaryMatrix.get(i, mid):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            res.append(binarySearch(i))\n",
    "        res = min(res)\n",
    "        return res if res < n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# This is just an example API. Don't uncomment this code.\n",
    "# class BinaryMatrix(object):\n",
    "#     def get(self, row: int, col: int) -> int:\n",
    "#     def dimensions(self) -> list:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        rows, cols = binaryMatrix.dimensions()\n",
    "        min_col = cols  # 初始化最左列为矩阵的列数\n",
    "        \n",
    "        for row in range(rows):\n",
    "            # 对每一行使用二分查找\n",
    "            low, high = 0, cols - 1\n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "                if binaryMatrix.get(row, mid) == 1:\n",
    "                    min_col = min(min_col, mid)\n",
    "                    high = mid - 1  # 继续在左侧搜索\n",
    "                else:\n",
    "                    low = mid + 1  # 继续在右侧搜索\n",
    "\n",
    "        # 检查是否找到至少一个1\n",
    "        if min_col == cols:\n",
    "            return -1\n",
    "        return min_col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        m, n = binaryMatrix.dimensions()\n",
    "        small_index = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            left, right = 0, n - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if binaryMatrix.get(i, mid) < 1:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    if mid == 0 or binaryMatrix.get(i, mid-1) < 1:\n",
    "                        small_index = min(small_index, mid)\n",
    "                        break\n",
    "                    right = mid - 1\n",
    "        return small_index if small_index != float(\"inf\") else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "\n",
    "        # 类似二分查找的思想。从右下角开始，遇到1往左走(因为想找到包含 1 的最左端列的索引)，遇到0往上走(看看本列还有没有1)，走到第一行，答案就很显然了.\n",
    "        dims = binaryMatrix.dimensions()\n",
    "        row, col = dims[0]-1, dims[1]-1\n",
    "        ans = -1\n",
    "        while row >= 0: # we break when we finish the first row\n",
    "            if binaryMatrix.get(row, col) == 1:\n",
    "                # go left\n",
    "                if col == 0:\n",
    "                    return 0 # as we cannot go beyond the first col\n",
    "                ans = col # record the current col as we don't know if the next one is zero or 1\n",
    "                col -= 1\n",
    "            else:\n",
    "                row -= 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is BinaryMatrix's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class BinaryMatrix(object):\n",
    "#    def get(self, row: int, col: int) -> int:\n",
    "#    def dimensions(self) -> list[]:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        row, col = binaryMatrix.dimensions()\n",
    "\n",
    "        def check(x, y):\n",
    "            return binaryMatrix.get(x, y)\n",
    "\n",
    "        ans = col + 1\n",
    "        for i in range(row):\n",
    "            j = 0\n",
    "            k = min(col-1, ans)\n",
    "            while j < k - 1:\n",
    "                mid = j + (k-j)//2\n",
    "                if check(i, mid) == 1:\n",
    "                    k = mid\n",
    "                else:\n",
    "                    j = mid\n",
    "            if j < ans and check(i, j) == 1:\n",
    "                ans = j\n",
    "            if k < ans and check(i, k) == 1:\n",
    "                ans = k\n",
    "        return ans if ans < col + 1 else -1        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# This is just an example API. Don't uncomment this code.\n",
    "# class BinaryMatrix(object):\n",
    "#     def get(self, row: int, col: int) -> int:\n",
    "#     def dimensions(self) -> list:\n",
    "\n",
    "class Solution:\n",
    "    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:\n",
    "        rows, cols = binaryMatrix.dimensions()\n",
    "        min_col = cols  # 初始化最左列为矩阵的列数\n",
    "        \n",
    "        for row in range(rows):\n",
    "            # 对每一行使用二分查找\n",
    "            low, high = 0, cols - 1\n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "                if binaryMatrix.get(row, mid) == 1:\n",
    "                    min_col = min(min_col, mid)\n",
    "                    high = mid - 1  # 继续在左侧搜索\n",
    "                else:\n",
    "                    low = mid + 1  # 继续在右侧搜索\n",
    "\n",
    "        # 检查是否找到至少一个1\n",
    "        if min_col == cols:\n",
    "            return -1\n",
    "        return min_col\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
